| |
| description |
208 pages
|
|
This thesis investigates the relationship between the ambiguity
functions for context-free grammars and for context-free languages.
It also examines which functions are ambiguity functions and how
different ambiguity classes relate to each other. The results can be
applied to generalise known results on sequential and parallel
parsing of context-free grammars.
To understand the main results we define some notions briefly:
The ambiguity of a word with respect to a context-free grammar is
the number of its derivation trees. The ambiguity function of a
context-free grammar maps an integer n to the maximal ambiguity of a
word whose length is bounded by n. A context-free language L is
f-ambiguous if f is the ambiguity function of some context-free
grammar generating L and, roughly speaking, no context-free grammar
generating L has a substantially lower ambiguity. A function is an
inherent ambiguity function if there is an f-ambiguous context-free
language. A homomorphism which maps a symbol either to itself or to
the empty word is called a projection. A symbol a is called bounded
in a language L if there is a constant c such that no word in L has
more than c occurrences of the symbol a. A projection is a bounded
contraction for a language L if it erases only symbols which are
bounded in L.
The main results are:
1. The set of ambiguity functions for cycle-free context-free
grammars and the set of inherent ambiguity functions coincide.
2. A technical statement which implies the following two facts:
2.1. The class of context-free languages with polynomially bounded
ambiguity is the closure of the class of unambiguous context-free
languages under bounded contractions.
2.2. Each reduced cycle-free context-free grammar G is either
exponentially ambiguous or its ambiguity is bounded by a polynomial
which can be computed from G. (2.2. was already part of the authors
Diploma thesis, but the new proof yields in many cases a better
polynomial (a polynomial with a lower degree), but never a worse
polynomial.)
3. For each computable divergent total non-decreasing function f
there is a divergent ambiguity function g such that g(n) is lower
than or equal to f(n) for each positive integer n. In fact, the same
ambiguity functions occur for the generation of rational trace
languages over special independence alphabets. (A rational trace
language T is generated by a regular (word) language R if T is the
set of traces which are represented by the words in R. The ambiguity
of a trace t is the number of representatives in R. It is now
straightforward to define the ambiguity function for the generation
of T by R.)
In addition the thesis contains generalisations for known results on
sequential and parallel parsing of context-free grammars. In
particular, the thesis considers the (sequential) Earley parsing
time of context-free grammars with sublinear ambiguity functions
(known to exist due to result 3). Moreover it is shown that each
reduced context-free grammars with a polynomially bounded ambiguity
can be parsed in logarithmic time on a CREW-PRAM. This is an
immediate consequence of 2.1. and a known result for the parallel
parsing time of unambiguous context-free grammars.
|
| publisher |
Stuttgart, Germany, Universität Stuttgart
|
| type |
Text
|
| Doctoral Thesis
|
| source |
ftp://ftp.informatik.uni-stuttgart.de/pub/library/ncstrl.ustuttgart_fi/DIS-2005-01/DIS-2005-01.pdf
|
| contributor |
FMI, Theoretische Informatik
|
| format |
application/pdf
|
| 1105100 Bytes
|
| subject |
Grammars and Other Rewriting Systems (CR F.4.2)
|
| Formal Languages (CR F.4.3)
|
| formal language
|
| context-free grammar
|
| ambiguity
|